1. Field of the Invention
The present invention relates to an associative memory comprising a function to extend a width of data to be retrieved for match detection to a plurality of words, that is, a function to detect an integrated match condition in such a case that the match conditions are respectively detected during continual retrievals for several times.
2. Description of the Prior Art
An associative memory (Content Addressable Memory) which stores each digital data in each one of a plurality of arranged memory words and receives, as an input, a retrieval data in order to retrieve memory words which have stored digital data having bit patterns matched with the entire part of the inputted retrieval data or a predetermined part of the bit pattern has been proposed.
FIG. 1 is a block diagram of the circuit illustrating an example of the associative memory.
This associative memory 10 is provided with many memory words 11.sub.-- 1, 11.sub.-- 2, . . . 11.sub.-- n which are composed of memory cells of m bits which are arranged each other in the lateral direction of the figure to form one word. Moreover, this associative memory 10 is provided with a retrieval data register 12 to which a retrieval data of one word is inputted and latched. Thereby, matching or mismatching between the entire part of the retrieval data latched in the retrieval data register 12 or a predetermined part of the bit pattern and the bit pattern corresponding to such bit pattern among the storage data stored in the memory words 11.sub.-- 1, 11.sub.-- 2, . . . 11.sub.-- n is detected to output a coincident signal of logic "1" (assumed as 5 V, in this case) to the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n corresponding to the memory words 11.sub.-- 1, 11.sub.-- 2, . . . 11.sub.-- n of which bit patterns are matched among the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n provided corresponding to the respective memory words 11.sub.-- 1, 11.sub.-- 2, . . . 11.sub.-- n. The other match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are maintained at the logic "0" (assumed as 0 V, in this case).
The signals outputted to these match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are stored in each flag register 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n. Here, it is assumed, as an example, as illustrated in the figure, that "0", "1", "1", "0", . . . , "0", "0" are respectively stored in each flag register 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n. The signals stored in these flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n are then inputted to a priority encoder 16. To the priority encoder 16, an encode pulse EP is inputted. For each input of the encode pulse EP, an address signal AD corresponding to a flag register having higher priority among the flag registers (two flag registers of 15.sub.-- 2 and 15.sub.-- 3, in this case) in which the logic "1" is stored is sequentially outputted in accordance with the predetermined priority. Here, a younger subscript means a higher priority. Therefore, when only one encode pulse EP is inputted, a memory address corresponding to the flag register 15.sub.-- 2 is outputted. An address signal AD outputted from the priority encoder 16 is then inputted as required to an address decoder 17. The address decoder 17 decodes this input address signal AD and outputs an access signal (a signal of logic "1", in this case) to the desired one word line (word line 18.sub.-- 2, in this case) corresponding to the inputted address signal AD among the word lines 18.sub.-- 1, 18.sub.-- 2, . . . , 18.sub.-- n provided respectively corresponding to each memory word 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. Thereby, the storage data stored in the memory word 11.sub.-- 2 corresponding to the word line 18.sub.-- 2 to which the access signal is outputted is read by an output register 19.
Next, when another encode pulse EP is also inputted, an address of the memory word 11.sub.-- 3 corresponding to the flag register 15.sub.-- 3 can, in turn, be obtained.
As explained above, an associative memory 10 is structured to retrieve the data stored in many memory words. 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n using whole part or predetermined part of the retrieval data in order to obtain the address of memory word having the coincident storage data and to read the data as a whole stored in such memory word as required.
For the associative memory having the basic structure as described above, the technology for expanding data width as the match retrieval object up to two or more words has been proposed.
FIG. 2 is a block diagram illustrating an example of the associative memory having a data width expanding function. The composing elements corresponding to that of the associative memory illustrated in FIG. 1 are denoted by the reference numerals like those in FIG. 1 and explanation about these elements is not repeated here.
Match lines 14.sub.-- 1, 14.sub.-- 2, . . . expanding from the memory words 11.sub.-- 1, 11.sub.-- 2, . . . are respectively connected to one input terminals of AND gates 20.sub.-- 1, 20.sub.-- 2, . . . Moreover, output terminals of OR gates 21.sub.-- 2, 21.sub.-- 3, . . . are connected to the other input terminals of the AND gates 20.sub.-- 1, 20.sub.-- 2, . . . and input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . are connected to a first retrieval control line 22. However, the OR gate corresponding to the upper most AND gate 20.sub.-- 1 of the figure is omitted and the first retrieval control line 22 is connected in direct to the input terminal of such AND gate 20.sub.-- 1.
Output terminals of the AND gates 20.sub.-- 1, 20.sub.-- 2, . . . are connected to data input terminals of first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , while output terminals of the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . are connected to input terminals of second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . Output terminals of the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . are connected to the priority encoder 16 illustrated in FIG. 1 (not illustrated in FIG. 2) and also connected to the input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . corresponding to adjacent memory words illustrated in the lower part of FIG. 2.
Each pair among the first and second flag registers 23.sub.-- 1, 24.sub.-- 1 . . . ; 23.sub.-- 2, 24.sub.-- 2, . . . corresponding with each other corresponds to the flag registers 15.sub.- 1, 15.sub.-- 2, . . . shown in FIG. 1.
A match result latch signal S1 to be outputted to a match result latch control line 25 is inputted to both of the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . and the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . This match result latch signal S1 latches an input data inputted from each of the data input terminal. More specifically, an input data at the rise timing "a" of the match result latch signal S1 is latched in the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , while an input data at the fall timing "b" of the match result latch signal S1 is latched in the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . .
In the associative memory configurated as explained above, match is retrieved as explained hereunder. Here, as illustrated in the figure, the data A, B, C, D, C, F, . . . are assumed to be stored in the memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, 11.sub.-- 4, 11.sub.-- 5, 11.sub.-- 6, . . . , respectively.
Here, on the occasion of individually retrieving each stored data, a first retrieval timing signal S2 is outputted to the first retrieval control line 22 at the time of inputting the retrieval data REF.sub.-- DATA for the purpose of retrieval operation. When the data "B" is assumed to be inputted as the retrieval data REF.sub.-- DATA, a match signal of logic "1" is outputted to the match line 14.sub.-- 2 corresponding to the memory word 11.sub.-- 2 in which the data "B" is stored and is then outputted to the AND gate 20.sub.-- 2. Simultaneously, the first retrieval timing signal S2 is also inputted to the AND gate 20.sub.-- 2 via the OR gate 21.sub.-- 2, causing the AND gate 20.sub.-- 2 to output a signal of logic "1". In this case, since a signal of logic "0" is outputted to the other match lines 14.sub.-- 1; 14.sub.-- 3, 14.sub.-- 4, . . . , the corresponding other AND gates 20.sub.-- 1; 20.sub.-- 3, 20.sub.-- 4, . . . output a signal of logic "0".
The signal of logic "1" outputted from the AND gate 20.sub.- 2 is latched in the first flag register 23.sub.-- 2 at the rise timing "a" of the match result latch signal S1 outputted to the match result latch control line 25 and is also latched in the second flag register 24.sub.-- 2 at the subsequent fall timing "b" of the match result latch signal S1.
Moreover, a signal of logic "0" is latched in the other first flag registers 23.sub.-- 1; 23.sub.-- 3, 23.sub.-- 4 . . . and the other second flag registers 24.sub.-- 1; 24.sub.-- 3, 24.sub.-- 4 . . . at each timing where a signal of logic "1" is latched in the first flag register 23.sub.-- 2 and the second flag register 24.sub.-- 2.
The signals of logic "0", "1", "0", . . . latched in the second flag registers 24.sub.-- 1, 24.sub.-- 2, 24.sub.-- 3, . . . are inputted to the priority encoder 16 illustrated in FIG. 1 as described above and thereby the address signal AD of the memory word 11.sub.-- 2 can be obtained.
Next, the retrieval for data of the extended width will then be explained. Here, the retrieval operation for data of two words composed of data "B" and data "C" which are extended to two words will be explained.
In this case, retrieval is performed first for the data "B" like the case explained above. Thereby, a signal of logic "1" is latched in the first and second flag registers 23.sub.-- 2, 24.sub.-- 2 corresponding to the memory word 11.sub.-- 2. Next, the retrieval is performed by inputting the data "C" as the retrieval data REF.sub.-- DATA. In this case, the first retrieval timing signal S2 is not outputted to the first retrieval control line 22, maintaining this line in the state of logic "0". When the retrieval is performed by inputting the data "C" as the retrieval data REF.sub.-- DATA, a match signal of logic "1" is outputted to the match lines 14.sub.-- 3, 14.sub.-- 5 corresponding respectively to a couple of memory words 11.sub.-- 3, 11.sub.-- 5 illustrated in the figure. However, since the signal of logic "1" latched in the second flag register 24.sub.-- 2 is inputted to the OR gate 21.sub.-- 3, the match signal of the match line 14.sub.-- 3 passes the AND gate 20.sub.-- 3 and the signal of logic "1" indicating the match condition is latched in the first and second flag registers 23.sub.-- 3, 24.sub.-- 3. On the other hand, since a signal of logic "0" latched in the second flag register 24.sub.-- 4 is inputted to the OR gate 21.sub.-- 5, a match signal of the match line 14.sub.-- 5 is cut off with the AND gate 20.sub.-- 5 and a signal of logic "0" indicating mismatch is latched in the first and second flag registers 23.sub.-- 5, 24.sub.-- 5. As described, match of two words data consisting of a pair of data "B" and data "C" can be detected. Coincidence of data of three or more words can also be detected in the same manner.
The associative memory illustrated in FIG. 2 is provided with a data width expanding function, but the data to be extended up to two or three words, etc. must be stored in the predetermined sequence in the adjacent memory words. Therefore, if a plurality of data to be retrieved are stored in the memory words separated from each other or if stored in the inverse sequence, that is, stored in the sequence of data "C" and data "B", detection of match of a plurality of combined data is no longer possible.
Example of a data format which requires the retrieval described above is illustrated in FIG. 3. FIG. 3 illustrates a data format wherein four data sets given respectively the attributes I, II, III, IV form one data group. As an example, in view of making obvious the concept of the data group and attributes, each data group of each group number 1, 2, 3, 4, . . . indicates the data belonging to an individual, while the attribute I indicates a name of a person and II, date of birth, and III, address . . .
Here, an example of retrieving data group of the group number 1, for example, while retrieving the data group consisting of a plurality of data given the attributes I, II, III, IV stored in the associative memory, will be explained. In this case, it is necessary that not only the remaining data "C", "D" of the match data group are read by sequentially retrieving the data "A" and data "B", but also the remaining data "B", "C" are read by retrieving the data "A" and "D" and moreover the data "A" is retrieved after retrieving the data "B".
However, the retrieval explained above is impossible for the aforementioned associative memory (refer to FIG. 2) provided with the word width expanding function. Moreover, in the associative memory described above, when the data "A" and data "B" are retrieved, it is impossible to discriminate a pair of data "A" having the attribute I and the data "B" having the attribute II in the column of the group number 1 illustrated in FIG. 3 from a pair of data "A" having the attribute II and the data "B" having the attribute III in the column of the group number 4. For instance, when it is required, on the basis of the attribute I indicating "name" and attribute II indicating "date of birth" to know the attributes III and IV of particular persons whose attribute I and the attribute II are matched, noise other than the necessary information such as detection of match of a pair of the attributes II and III may be mixed.
An associative memory which has solved the problem explained above has been proposed by the same applicant of the present invention (refer to Japanese Patent Application No. HEI 5-248121). This patent is not yet published as the laid-open patent but an associative memory incorporated to this application will be explained as the related art.
FIG. 4 is a block diagram illustrating an example of the associative memory incorporated to above patent application. The composing elements same as those of the associative memory illustrated in FIG. 2 are designated by the reference numerals like those given in FIG. 2 and only different points will be explained.
Each memory words 11.sub.-- 1, 11.sub.-- 2, . . . is composed of an attribute storing part 11.sub.-- 1.sub.-- 1, 11.sub.-- 2.sub.-- 1, . . . for storing attributes and a data storing part 11.sub.-- 1.sub.-- 2, 11.sub.-- 2.sub.-- 2, . . . for storing data to respectively store data consisting of a pair of attribute and data corresponding with each other. Here, as illustrated in the figure, data "A" of the attribute I; data "B" of the attribute II; data "C" of the attribute III and data "D" of the attribute IV belonging to the group number 1 illustrated in FIG. 3 are respectively stored in the memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3 and 11.sub.-- 4. Moreover, data "C" of the attribute I; data "F" of the attribute II, . . . belonging to the group number 2 illustrated in FIG. 3 are stored respectively in the memory words 11.sub.-- 5, 11.sub.-- 6, . . . For the retrieval operation, the retrieval data REF.sub.-- DATA consisting of a pair of attribute and data is inputted.
The memory words 11.sub.-- 1, 11.sub.-- 2 are provided with match lines 14.sub.-- 1, 14.sub.-- 2, . . . to which a match signal is outputted when the storage data (both attribute and data) stored in the memory word is matched with the input retrieval data (both attribute and data) and attribute match lines 30.sub.-- 1, 30.sub.-- 2, . . . to which only attribute match/mismatch signal is outputted. Match of only attribute and match of both attribute and data can be detected with the circuit having the similar structure to the match detection circuit of the prior art. Since the match detection circuit of the prior art is obvious for those skilled in the art of the associative memory, it is neither illustrated nor explained here.
Corresponding to the memory words 11.sub.-- 1, 11.sub.-- 2, third flag registers 31.sub.-- 1, 31.sub.-- 2, . . . are prepared and the attribute match lines 30.sub.-- 1, 30.sub.-- 2, . . . are extended to data input terminals of the corresponding third flag registers 31.sub.-- 1, 31.sub.-- 2, . . . Moreover, this associative memory is provided with data lines 32.sub.-- 1, 32.sub.-- 2, . . . one by one respectively for a memory word group consisting of a plurality of memory words to which data belonging to each data group illustrated in FIG. 3 is stored and also provided with first switches 33.sub.-- 1, 33.sub.-- 2, . . . between the data lines 32.sub.-- 1, 32.sub.-- 2, . . . and the output terminals of second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . These first switches 33.sub.-- 1, 33.sub.-- 2, . . . are practically formed of transistors, etc. The other switches explained later are also formed in the same manner. The first switches 33.sub.-- 1, 33.sub.-- 2, . . . are switched on when a signal of logic "1" is latched in the corresponding third flag registers 31.sub.-- 1, 31.sub.-- 2, . . . and are cut off when a signal of logic "0" is latched therein. The third flag registers 31.sub.-- 1, 31.sub.-- 2, . . . latch the signals of the corresponding attribute match lines 30.sub.-- 1, 30.sub.-- 2, . . . at the fall timing "b" of the match result latch signal S1 outputted to the match result latch control line 25.
In addition, second switches 34.sub.-- 1, 34.sub.-- 2, . . . are also prepared between the data lines 32.sub.-- 1, 32.sub.-- 2, . . . and the input terminals of the OR gates 21.sub.-- 1, 21.sub.-- 2, . . . and these second switches 34.sub.-- 1, 34.sub.-- 2, . . . are controlled by the signal from the corresponding attribute match lines 30.sub.-- 1, 30.sub.-- 2, . . . to be switched on when the signal is logic "1" indicating the match condition or to be cut off when the signal is logic "0" indicating mismatch condition. Different from the associative memory illustrated in FIG. 2, an OR gate 21.sub.-- 1 is also provided in the preceding stage of the AND gate 20.sub.-- 1 corresponding to the memory word 11.sub.-- 1 at the upper most stage of the figure in the associative memory illustrated in FIG. 4.
In the associative memory configurated as explained above, retrieval of match is performed as explained hereunder.
Since individual data retrieval of one word and the first retrieval among the retrievals of a plurality of continuous words is performed in the same manner as the associative memory with the word expanding function of the prior art illustrated in FIG. 2, explanation about the first retrieval is omitted here. Here it is assumed that logic "1" is latched, during the first retrieval, in the first and second flag registers 23.sub.-- 2, 24.sub.-- 2 corresponding to the memory word 11.sub.-- 2 with the retrieval data REF.sub.-- DATA consisting of the attribute II and data "B". In this case, a signal of logic "1" is outputted, upon matching of the attribute, to the attribute match line 30.sub.-- 2 corresponding to the memory word 11.sub.-- 2 and thereby a signal of logic "1" is also latched in the corresponding third flag register 31.sub.-- 2. Accordingly, the corresponding first switch 33.sub.-- 2 is switched on and a signal of logic "1" indicating match of both attribute and data stored in the corresponding second flag register 24.sub.-- 2 is outputted-to the data line 32.sub.-- 1. Simultaneously, the corresponding second switch 34.sub.-- 2 is also switched on, but it is useless operation in the first retrieval operation.
Next, it is assumed that the retrieval is performed by inputting the retrieval data REF.sub.-- DATA consisting of the attribute IV and data "D". In this case, like the associative memory of FIG. 2, the first retrieval control line 22 is maintained at the logic "0". In this timing, upon reception of signal indicating match of attribute, a signal of logic "1" is outputted to the attribute match line 30.sub.-- 4 corresponding to the memory word 11.sub.-- 4 and thereby the corresponding second switch 34.sub.-- 4 is turned on, inputting a signal of logic "1" of the second flag register 24.sub.-- 2 corresponding to the memory word 11.sub.-- 2 being outputted to the data line 32.sub.-- 1 is then inputted to the AND gate 20.sub.-- 4 via the OR gate 21.sub.-- 4. Therefore, match of both attribute IV and data "D" is detected by the memory word 11.sub.-- 4 and a match signal of logic "1" is outputted to the match line 14.sub.-- 4. Then a signal of logic "1" is latched in the corresponding first and second flag registers 23.sub.-- 4, 24.sub.-- 4 with the match result latch signal S1 outputted to the match result latch control line 25. Also, in this case, a signal of logic "1" outputted to the attribute match line 30.sub.-- 4 is latched in the corresponding third flag register 31.sub.-- 4, the corresponding first switch 33.sub.-- 4 is turned on and a signal of logic "1" of the second flag register 24.sub.-- 4 is outputted to the data line 32.sub.-- 1. In this second retrieval, since logic "0" indicating mismatch of attribute is outputted to the attribute match line 30.sub.-- 2 corresponding to the memory word 11.sub.-- 2, "0" is stored in the corresponding third flag register 31.sub.-- 2 and the first switch 33.sub.-- 2 corresponding to the memory word 11.sub.-- 2 turns off.
Thereby, a signal of logic "1" of the second flag register 24.sub.-- 4 corresponding to the memory word 11.sub.-- 4 is inputted to the priority encoder 16 (refer to FIG. 1) and an address of the memory word 11.sub.-- 4 can be obtained. However, it is previously known that the attribute IV is stored in the memory word 11.sub.-- 4 and if it is requested to read data, for example, of the attribute III in the same group, an address of the memory word 11.sub.-- 3 is obtained by subtracting one from the address obtained and this address is then inputted to the address decoder 17 to read contents of the memory word 11.sub.-- 3.
Meanwhile, when retrieval is carried out with a retrieval data consisting, for example, of the attribute IV and data "B", in place of the retrieval data consisting of the attribute IV and data "D" as the second retrieval operation, the second switch 34.sub.-- 4 is switched on because of match of attribute and a signal of logic "1" outputted on the data line 32.sub.-- 1 is fetched for the memory word 11.sub.-- 4, but since data is different, the logic "0" indicating mismatch of data is outputted to the match line 14.sub.-- 4 and the logic "0" indicating mismatch is latched in the first and second flag registers 23.sub.-- 4 and 24.sub.-- 4. Moreover, attribute is mismatched for the memory word 11.sub.-- 2 for which the data "B" is matched and thereby both attribute and data are not matched.
As described, in the associative memory illustrated in FIG. 4, the retrieval may be performed in the same group even when it is conducted for the data stored in the memory words separated from each other or the data in the inverse sequence.
Here, the data lines 32.sub.-- 1, 32.sub.-- 2, . . . of the associative memory illustrated in FIG. 4 are fixed in the length thereof under the supposition that the number of data belonging to one group is predetermined, but when the data lines of the fixed length are provided, the maximum number of data belonging to one group must be estimated to provide the data lines corresponding to such maximum number of data. As a result, useless memory words may be generated in such a case that data group is formed with the number of data smaller than the maximum number of data. Therefore, it is preferable that the data lines are set in the variable length in accordance with the number of data belonging to one group.
FIG. 5 is a schematic view illustrating a system for realizing variable length data lines.
The data line 32 is extended over a plurality of memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, . . . and is provided with switches 40.sub.-- 1, 40.sub.-- 2, 40.sub.-- 3, . . . connected in series corresponding respectively to the other memory words 11.sub.-- 2, 11.sub.-- 3, . . . except for the upper most memory word 11.sub.-- 1. The switches 40.sub.-- 2, 40.sub.-- 3, 40.sub.-- 4, . . . are arranged between the corresponding memory words 11.sub.-- 2, 11.sub.-- 3, 11.sub.-- 4, . . . and the adjacent memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, . . . provided at just upper stage of the corresponding ones. The every other switches 40.sub.-- 2, 40.sub.-- 4, 40.sub.-- 6, . . . among the switches 40.sub.-- 2, 40.sub.-- 3, 40.sub.-- 4, . . . are switched on with the first switch control signal outputted to the first control line 41 and every fourth switches 40.sub.-- 3, 40.sub.-- 7, . . . are switched on with the second switch control signal outputted to the second control line 42 and the every ninth switches 40.sub.-- 5, . . . among the remaining switches are switched on with the third switch control signal outputted to the third control line 43.
When the number of data forming one data group is 2, every other switches 40.sub.-- 2, 40.sub.-- 4, 40.sub.-- 6, . . . are switched on by outputting the first switch control signal to the first control line 41. Thereby, the data lines disconnected for every two memory words 11.sub.-- 1, 11.sub.-- 2; 11.sub.-- 3, 11.sub.-- 4; 11.sub.-- 5, 11.sub.-- 6; . . . are formed. In addition, when the number of data forming one data group is 4, the first switch control signal is outputted to the first control line 41 and the second switch control signal is outputted to the second control line 42. Thereby, the data lines disconnected for every four memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, 11.sub.-- 4; 11.sub.-- 5, 11.sub.-- 6, . . . are formed. In the same manner, the number of data forming one data group is 8, the first and second switch control signals are outputted respectively to the first control line 41 and the second control line 42 and the third switch control signal is outputted to the third control line 43. Thereby, the data lines disconnected for every eight memory words 11.sub.-- 1, . . . , 11.sub.-- 8; 11.sub.-- 9, . . . are formed.
According to this system, when the number of data forming one data group is 2.sup.n, any vacant one is generated in the memory words, but such number is, for example, 3, 5, 9, etc., other than 2.sup.n, vacant memory words may be generated. When a structure is formed so that many switches 40.sub.-- 2, 40.sub.-- 3, . . . can be switched on or off as desired in order to avoid generation of vacant memory words, the number of control lines increases and the control circuit for outputting switch control signals to these control lines may be complicated. Therefore, the system illustrated in FIG. 5 is not suitable for perfect control of the data line length.
FIG. 6 is a schematic diagram illustrating another system for realizing variable length data lines.
This system is similar to FIG. 5 in the points that the data line 32 is extended over many memory words and is provided with the switches 40.sub.-- 2, 40.sub.-- 3, 40.sub.-- 4, . . . connected in series with each other corresponding respectively to the memory words other than the memory word at the upper most end. Each memory word is provided with each attribute storing part 11.sub.-- 1.sub.-- 1, 11.sub.-- 2.sub.-- 1, 11.sub.-- 3.sub.-- 1, . . . to respectively store each attribute I, II, III, IV illustrated in the figure. This example is structured so that the corresponding switch is controlled for on or off state depending on that the attribute stored in the attribute storing part 11.sub.-- 1.sub.-- 1, 11.sub.-- 2.sub.-- 1, 11.sub.-- 3.sub.-- 1, . . . is attribute I or other attributes II, III, IV, that is, the corresponding switch is maintained in the off state when the attribute is I or is switched on when the attribute is II, III or IV. This structure automatically enables formation of data lines disconnected for the right number of memory words by arranging the data of attribute I at the leading part of each data group without relation to the number of data forming one data group or even if data group of different number of data is mixed.
FIG. 7 is a circuit diagram illustrating an example of an attribute deciding circuit for deciding whether the attribute is I or not.
In this case, "000" is assigned for the attribute I and when the attribute stored in the attribute storing part 11.sub.-- i.sub.-- l is I ("000"), "0" is outputted from the OR gate. Therefore, the switch formed of a transistor 40 is turned off and both data lines of the transistor 40' are electrically disconnected. When the attribute stored in the attribute storing part 11.sub.-- i.sub.-- l is other than I, "1" is outputted from the OR gate, the transistor 40 is turned on, and the data lines in both sides of the transistor are connected.
As described, length of the data lines 32.sub.-- 1, 32.sub.-- 2, . . . can be adjusted depending on the number of data forming one data group in the associative memory illustrated in FIG. 4. Here, it is of course possible to adjust the length of data lines by controlling the switches with the exclusive control lines, in place of utilizing attribute data.
An associative memory is accompanied by requirement for reduction of power consumption like the other ordinary RAM memory, etc. In an ordinary RAM memory, an address is inputted for making access to memory words of such address. Therefore, reduction of power consumption can be realized by dividing many memory words into many blocks and then making active, depending on the input address, only the block including the memory word designated by such input address.
However, an associative memory retrieves the memory words, by inputting a retrieval data, in which the data matching with the input retrieval data is stored. Therefore, if the memory words are divided into blocks, it is unknown in which memory word of which block match can be detected. Accordingly, all blocks must be made active and it is impossible to reduce power consumption only with dividing memory words into many blocks.
The Japanese Patent Application Laid-open No. HEI 3-212896 describes that an associative memory array is divided for every plural arrangements of one direction to form blocks, a block selecting means of selecting any one block is provided so that power consumption of the associative memory can be reduced by comparing only the block selected by this block selecting means with the retrieval data.
However, this technique described in the Japanese Patent Application Laid-open No. HEI 3-212896 has disadvantages that a memory block selecting information must be previously set at a part of the input address for the retrieval operation and moreover an extra hardware and processing time are required for attaining such requirement.